#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;
/**
 *
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
 * */

// todo 其实就是字符串那个能不能......类似于那个不同路径 ...反正不知道跟哪个字符串题很像
bool isInterleave(string s1, string s2, string s3) {
    int m = s1.size(), n = s2.size();
    if (s3.size() != m + n) return false;
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, false));
    dp[0][0] = true;
    //行操作dp[][0];
    //这边就得从1 开始 因为有一行一列没操作
    for (int i = 1; i <= m && s1[i - 1] == s3[i - 1]; ++i) {

        dp[i][0] = true;
    }

    for (int i = 1; i <= n && s2[i - 1] == s3[i - 1]; ++i) {

        dp[0][i] = true;
    }


    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            //这边还得&&一下
            dp[i][j] = (dp[i - 1][j] && s3[i + j - 1] == s1[i - 1]) || (dp[i][j - 1] && s3[i + j - 1] == s2[j - 1]);
        }
    }

    return dp[m][n];
}